package 剑指offer;


/**
 * Created by lenovo】 on 2017/2/24.
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 *
 * 思路：1. 找到最后一项，必定是根节点，向前找，
 *       2. 比它大的元素按顺序存到数组MAX
 *       3. 比它小的元素按顺序存到数组MIN
 *       4. 对数组MAX进行1,2,3的操作（递归）
 *       5. 对数组MIN进行1,2,3的操作（递归）
 *
 */
public class VerifySquenceOfBST {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence.length == 0) {
            return false;
        }
        int lenSequence = sequence.length;
        int lastElement = sequence[lenSequence - 1];
        int divide = 0;
        for (int i = 0; i < lenSequence - 1; i++) {
            int tmp = sequence[i];
            if (tmp < lastElement) {
                divide ++;
            }else {
                break;
            }
        }
        // 通过分界线拷贝成两个数组
        int lenMax = lenSequence - divide - 1;
        int lenMin = divide;
        int [] max = new int[lenMax];
        int [] min = new int[lenMin];
        System.arraycopy(sequence, 0, min, 0, lenMin);
        System.arraycopy(sequence, divide, max, 0, lenMax);
        // 判断是否满足条件
        for (int m1 : min) {
            if (m1 > lastElement) {
                return false;
            }
        }
        for (int m2 : max) {
            if (m2 < lastElement) {
                return false;
            }
        }
        if (min.length > 2) {
            VerifySquenceOfBST(min);
        }
        if (max.length > 2) {
            VerifySquenceOfBST(max);
        }
        return true;
    }
}
